From 48446574a6b3763f66d9a832481d379451d9ec91 Mon Sep 17 00:00:00 2001 From: Alex Crichton Date: Thu, 3 Nov 2016 17:18:48 -0700 Subject: [PATCH] Optimize resolution by removing allocations This commit is a relatively serious optimization pass of the resolution phase in Cargo, targeted at removing as many allocations as possible from this phase. Executed as an iterative loop this phase of Cargo can often be costly for large graphs but it's run on every single build! The main optimization here is to avoid cloning the context and/or pushing a backtracking frame if there are no candidates left in the current list of candidates. That optimizes a fast-path for crates with lock files (almost all of them) and gets us to the point where cloning the context basically disappears from all profiling. --- Cargo.lock | 62 +++---- src/bin/cargo.rs | 2 +- src/cargo/core/resolver/mod.rs | 315 ++++++++++++++++++++++----------- src/cargo/lib.rs | 2 +- src/cargo/util/graph.rs | 4 +- tests/resolve.rs | 4 +- 6 files changed, 252 insertions(+), 137 deletions(-) diff --git a/Cargo.lock b/Cargo.lock index 7a607b9e7..02a162478 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -25,7 +25,7 @@ dependencies = [ "log 0.3.8 (registry+https://github.com/rust-lang/crates.io-index)", "miow 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)", "num_cpus 1.5.0 (registry+https://github.com/rust-lang/crates.io-index)", - "openssl 0.9.12 (registry+https://github.com/rust-lang/crates.io-index)", + "openssl 0.9.13 (registry+https://github.com/rust-lang/crates.io-index)", "psapi-sys 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)", "rustc-serialize 0.3.24 (registry+https://github.com/rust-lang/crates.io-index)", "semver 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)", @@ -34,11 +34,11 @@ dependencies = [ "serde_ignored 0.0.3 (registry+https://github.com/rust-lang/crates.io-index)", "serde_json 1.0.2 (registry+https://github.com/rust-lang/crates.io-index)", "shell-escape 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)", - "tar 0.4.12 (registry+https://github.com/rust-lang/crates.io-index)", + "tar 0.4.13 (registry+https://github.com/rust-lang/crates.io-index)", "tempdir 0.3.5 (registry+https://github.com/rust-lang/crates.io-index)", "term 0.4.5 (registry+https://github.com/rust-lang/crates.io-index)", "toml 0.4.1 (registry+https://github.com/rust-lang/crates.io-index)", - "url 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)", + "url 1.4.1 (registry+https://github.com/rust-lang/crates.io-index)", "winapi 0.2.8 (registry+https://github.com/rust-lang/crates.io-index)", ] @@ -72,7 +72,7 @@ name = "backtrace" version = "0.3.2" source = "registry+https://github.com/rust-lang/crates.io-index" dependencies = [ - "backtrace-sys 0.1.10 (registry+https://github.com/rust-lang/crates.io-index)", + "backtrace-sys 0.1.11 (registry+https://github.com/rust-lang/crates.io-index)", "cfg-if 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)", "dbghelp-sys 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)", "kernel32-sys 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)", @@ -83,7 +83,7 @@ dependencies = [ [[package]] name = "backtrace-sys" -version = "0.1.10" +version = "0.1.11" source = "registry+https://github.com/rust-lang/crates.io-index" dependencies = [ "gcc 0.3.50 (registry+https://github.com/rust-lang/crates.io-index)", @@ -97,7 +97,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index" [[package]] name = "bitflags" -version = "0.8.2" +version = "0.9.1" source = "registry+https://github.com/rust-lang/crates.io-index" [[package]] @@ -121,10 +121,10 @@ dependencies = [ "rustc-serialize 0.3.24 (registry+https://github.com/rust-lang/crates.io-index)", "serde 1.0.8 (registry+https://github.com/rust-lang/crates.io-index)", "serde_json 1.0.2 (registry+https://github.com/rust-lang/crates.io-index)", - "tar 0.4.12 (registry+https://github.com/rust-lang/crates.io-index)", + "tar 0.4.13 (registry+https://github.com/rust-lang/crates.io-index)", "tempdir 0.3.5 (registry+https://github.com/rust-lang/crates.io-index)", "term 0.4.5 (registry+https://github.com/rust-lang/crates.io-index)", - "url 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)", + "url 1.4.1 (registry+https://github.com/rust-lang/crates.io-index)", "winapi 0.2.8 (registry+https://github.com/rust-lang/crates.io-index)", ] @@ -150,7 +150,7 @@ dependencies = [ "serde 1.0.8 (registry+https://github.com/rust-lang/crates.io-index)", "serde_derive 1.0.8 (registry+https://github.com/rust-lang/crates.io-index)", "serde_json 1.0.2 (registry+https://github.com/rust-lang/crates.io-index)", - "url 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)", + "url 1.4.1 (registry+https://github.com/rust-lang/crates.io-index)", ] [[package]] @@ -166,7 +166,7 @@ dependencies = [ "curl-sys 0.3.11 (registry+https://github.com/rust-lang/crates.io-index)", "libc 0.2.23 (registry+https://github.com/rust-lang/crates.io-index)", "openssl-probe 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)", - "openssl-sys 0.9.12 (registry+https://github.com/rust-lang/crates.io-index)", + "openssl-sys 0.9.13 (registry+https://github.com/rust-lang/crates.io-index)", "winapi 0.2.8 (registry+https://github.com/rust-lang/crates.io-index)", ] @@ -178,7 +178,7 @@ dependencies = [ "gcc 0.3.50 (registry+https://github.com/rust-lang/crates.io-index)", "libc 0.2.23 (registry+https://github.com/rust-lang/crates.io-index)", "libz-sys 1.0.13 (registry+https://github.com/rust-lang/crates.io-index)", - "openssl-sys 0.9.12 (registry+https://github.com/rust-lang/crates.io-index)", + "openssl-sys 0.9.13 (registry+https://github.com/rust-lang/crates.io-index)", "pkg-config 0.3.9 (registry+https://github.com/rust-lang/crates.io-index)", "winapi 0.2.8 (registry+https://github.com/rust-lang/crates.io-index)", ] @@ -280,8 +280,8 @@ dependencies = [ "libc 0.2.23 (registry+https://github.com/rust-lang/crates.io-index)", "libgit2-sys 0.6.11 (registry+https://github.com/rust-lang/crates.io-index)", "openssl-probe 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)", - "openssl-sys 0.9.12 (registry+https://github.com/rust-lang/crates.io-index)", - "url 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)", + "openssl-sys 0.9.13 (registry+https://github.com/rust-lang/crates.io-index)", + "url 1.4.1 (registry+https://github.com/rust-lang/crates.io-index)", ] [[package]] @@ -292,7 +292,7 @@ dependencies = [ "curl 0.4.6 (registry+https://github.com/rust-lang/crates.io-index)", "git2 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)", "log 0.3.8 (registry+https://github.com/rust-lang/crates.io-index)", - "url 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)", + "url 1.4.1 (registry+https://github.com/rust-lang/crates.io-index)", ] [[package]] @@ -315,7 +315,7 @@ version = "0.1.2" source = "registry+https://github.com/rust-lang/crates.io-index" dependencies = [ "matches 0.1.4 (registry+https://github.com/rust-lang/crates.io-index)", - "unicode-bidi 0.3.2 (registry+https://github.com/rust-lang/crates.io-index)", + "unicode-bidi 0.3.3 (registry+https://github.com/rust-lang/crates.io-index)", "unicode-normalization 0.1.4 (registry+https://github.com/rust-lang/crates.io-index)", ] @@ -365,7 +365,7 @@ dependencies = [ "libc 0.2.23 (registry+https://github.com/rust-lang/crates.io-index)", "libssh2-sys 0.2.6 (registry+https://github.com/rust-lang/crates.io-index)", "libz-sys 1.0.13 (registry+https://github.com/rust-lang/crates.io-index)", - "openssl-sys 0.9.12 (registry+https://github.com/rust-lang/crates.io-index)", + "openssl-sys 0.9.13 (registry+https://github.com/rust-lang/crates.io-index)", "pkg-config 0.3.9 (registry+https://github.com/rust-lang/crates.io-index)", ] @@ -377,7 +377,7 @@ dependencies = [ "cmake 0.1.24 (registry+https://github.com/rust-lang/crates.io-index)", "libc 0.2.23 (registry+https://github.com/rust-lang/crates.io-index)", "libz-sys 1.0.13 (registry+https://github.com/rust-lang/crates.io-index)", - "openssl-sys 0.9.12 (registry+https://github.com/rust-lang/crates.io-index)", + "openssl-sys 0.9.13 (registry+https://github.com/rust-lang/crates.io-index)", "pkg-config 0.3.9 (registry+https://github.com/rust-lang/crates.io-index)", ] @@ -525,14 +525,14 @@ dependencies = [ [[package]] name = "openssl" -version = "0.9.12" +version = "0.9.13" source = "registry+https://github.com/rust-lang/crates.io-index" dependencies = [ - "bitflags 0.8.2 (registry+https://github.com/rust-lang/crates.io-index)", + "bitflags 0.9.1 (registry+https://github.com/rust-lang/crates.io-index)", "foreign-types 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)", "lazy_static 0.2.8 (registry+https://github.com/rust-lang/crates.io-index)", "libc 0.2.23 (registry+https://github.com/rust-lang/crates.io-index)", - "openssl-sys 0.9.12 (registry+https://github.com/rust-lang/crates.io-index)", + "openssl-sys 0.9.13 (registry+https://github.com/rust-lang/crates.io-index)", ] [[package]] @@ -542,7 +542,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index" [[package]] name = "openssl-sys" -version = "0.9.12" +version = "0.9.13" source = "registry+https://github.com/rust-lang/crates.io-index" dependencies = [ "gcc 0.3.50 (registry+https://github.com/rust-lang/crates.io-index)", @@ -710,7 +710,7 @@ dependencies = [ [[package]] name = "tar" -version = "0.4.12" +version = "0.4.13" source = "registry+https://github.com/rust-lang/crates.io-index" dependencies = [ "filetime 0.1.10 (registry+https://github.com/rust-lang/crates.io-index)", @@ -779,7 +779,7 @@ dependencies = [ [[package]] name = "unicode-bidi" -version = "0.3.2" +version = "0.3.3" source = "registry+https://github.com/rust-lang/crates.io-index" dependencies = [ "matches 0.1.4 (registry+https://github.com/rust-lang/crates.io-index)", @@ -805,7 +805,7 @@ dependencies = [ [[package]] name = "url" -version = "1.4.0" +version = "1.4.1" source = "registry+https://github.com/rust-lang/crates.io-index" dependencies = [ "idna 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)", @@ -860,9 +860,9 @@ dependencies = [ "checksum aho-corasick 0.5.3 (registry+https://github.com/rust-lang/crates.io-index)" = "ca972c2ea5f742bfce5687b9aef75506a764f61d37f8f649047846a9686ddb66" "checksum aho-corasick 0.6.3 (registry+https://github.com/rust-lang/crates.io-index)" = "500909c4f87a9e52355b26626d890833e9e1d53ac566db76c36faa984b889699" "checksum backtrace 0.3.2 (registry+https://github.com/rust-lang/crates.io-index)" = "72f9b4182546f4b04ebc4ab7f84948953a118bd6021a1b6a6c909e3e94f6be76" -"checksum backtrace-sys 0.1.10 (registry+https://github.com/rust-lang/crates.io-index)" = "d192fd129132fbc97497c1f2ec2c2c5174e376b95f535199ef4fe0a293d33842" +"checksum backtrace-sys 0.1.11 (registry+https://github.com/rust-lang/crates.io-index)" = "3a0d842ea781ce92be2bf78a9b38883948542749640b8378b3b2f03d1fd9f1ff" "checksum bitflags 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)" = "aad18937a628ec6abcd26d1489012cc0e18c21798210f491af69ded9b881106d" -"checksum bitflags 0.8.2 (registry+https://github.com/rust-lang/crates.io-index)" = "1370e9fc2a6ae53aea8b7a5110edbd08836ed87c88736dfabccade1c2b44bff4" +"checksum bitflags 0.9.1 (registry+https://github.com/rust-lang/crates.io-index)" = "4efd02e230a02e18f92fc2735f44597385ed02ad8f831e7c1c1156ee5e1ab3a5" "checksum bufstream 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)" = "f2f382711e76b9de6c744cc00d0497baba02fb00a787f088c879f01d09468e32" "checksum cfg-if 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "de1e760d7b6535af4241fca8bd8adf68e2e7edacc6b29f5d399050c5e48cf88c" "checksum cmake 0.1.24 (registry+https://github.com/rust-lang/crates.io-index)" = "b8ebbb35d3dc9cd09497168f33de1acb79b265d350ab0ac34133b98f8509af1f" @@ -908,9 +908,9 @@ dependencies = [ "checksum num-rational 0.1.36 (registry+https://github.com/rust-lang/crates.io-index)" = "c2dc5ea04020a8f18318ae485c751f8cfa1c0e69dcf465c29ddaaa64a313cc44" "checksum num-traits 0.1.37 (registry+https://github.com/rust-lang/crates.io-index)" = "e1cbfa3781f3fe73dc05321bed52a06d2d491eaa764c52335cf4399f046ece99" "checksum num_cpus 1.5.0 (registry+https://github.com/rust-lang/crates.io-index)" = "f6e850c7f35c3de263e6094e819f6b4b9c09190ff4438fc6dec1aef1568547bc" -"checksum openssl 0.9.12 (registry+https://github.com/rust-lang/crates.io-index)" = "bb5d1663b73d10c6a3eda53e2e9d0346f822394e7b858d7257718f65f61dfbe2" +"checksum openssl 0.9.13 (registry+https://github.com/rust-lang/crates.io-index)" = "b34cd77cf91301fff3123fbd46b065c3b728b17a392835de34c397315dce5586" "checksum openssl-probe 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "d98df0270d404ccd3c050a41d579c52d1db15375168bb3471e04ec0f5f378daf" -"checksum openssl-sys 0.9.12 (registry+https://github.com/rust-lang/crates.io-index)" = "3a5886d87d3e2a0d890bf62dc8944f5e3769a405f7e1e9ef6e517e47fd7a0897" +"checksum openssl-sys 0.9.13 (registry+https://github.com/rust-lang/crates.io-index)" = "e035022a50faa380bd7ccdbd184d946ce539ebdb0a358780de92a995882af97a" "checksum pkg-config 0.3.9 (registry+https://github.com/rust-lang/crates.io-index)" = "3a8b4c6b8165cd1a1cd4b9b120978131389f64bdaf456435caa41e630edba903" "checksum psapi-sys 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "abcd5d1a07d360e29727f757a9decb3ce8bc6e0efa8969cfaad669a8317a2478" "checksum quote 0.3.15 (registry+https://github.com/rust-lang/crates.io-index)" = "7a6e920b65c65f10b2ae65c831a81a073a89edd28c7cce89475bff467ab4167a" @@ -932,7 +932,7 @@ dependencies = [ "checksum strsim 0.6.0 (registry+https://github.com/rust-lang/crates.io-index)" = "b4d15c810519a91cf877e7e36e63fe068815c678181439f2f29e2562147c3694" "checksum syn 0.11.11 (registry+https://github.com/rust-lang/crates.io-index)" = "d3b891b9015c88c576343b9b3e41c2c11a51c219ef067b264bd9c8aa9b441dad" "checksum synom 0.11.3 (registry+https://github.com/rust-lang/crates.io-index)" = "a393066ed9010ebaed60b9eafa373d4b1baac186dd7e008555b0f702b51945b6" -"checksum tar 0.4.12 (registry+https://github.com/rust-lang/crates.io-index)" = "ab0ef9ead2fe0aa9e18475a96a207bfd5143f4124779ef7429503a8665416ce8" +"checksum tar 0.4.13 (registry+https://github.com/rust-lang/crates.io-index)" = "281285b717926caa919ad905ef89c63d75805c7d89437fb873100925a53f2b1b" "checksum tempdir 0.3.5 (registry+https://github.com/rust-lang/crates.io-index)" = "87974a6f5c1dfb344d733055601650059a3363de2a6104819293baff662132d6" "checksum term 0.4.5 (registry+https://github.com/rust-lang/crates.io-index)" = "d168af3930b369cfe245132550579d47dfd873d69470755a19c2c6568dbbd989" "checksum thread-id 2.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "a9539db560102d1cef46b8b78ce737ff0bb64e7e18d35b2a5688f7d097d0ff03" @@ -940,11 +940,11 @@ dependencies = [ "checksum thread_local 0.2.7 (registry+https://github.com/rust-lang/crates.io-index)" = "8576dbbfcaef9641452d5cf0df9b0e7eeab7694956dd33bb61515fb8f18cfdd5" "checksum thread_local 0.3.3 (registry+https://github.com/rust-lang/crates.io-index)" = "c85048c6260d17cf486ceae3282d9fb6b90be220bf5b28c400f5485ffc29f0c7" "checksum toml 0.4.1 (registry+https://github.com/rust-lang/crates.io-index)" = "4cc5dbfb20a481e64b99eb7ae280859ec76730c7191570ba5edaa962394edb0a" -"checksum unicode-bidi 0.3.2 (registry+https://github.com/rust-lang/crates.io-index)" = "916219eb752dd865717c9b21064401c6ee843dc91ed659c144591e0c87c56d59" +"checksum unicode-bidi 0.3.3 (registry+https://github.com/rust-lang/crates.io-index)" = "a6a2c4e3710edd365cd7e78383153ed739fa31af19f9172f72d3575060f5a43a" "checksum unicode-normalization 0.1.4 (registry+https://github.com/rust-lang/crates.io-index)" = "e28fa37426fceeb5cf8f41ee273faa7c82c47dc8fba5853402841e665fcd86ff" "checksum unicode-xid 0.0.4 (registry+https://github.com/rust-lang/crates.io-index)" = "8c1f860d7d29cf02cb2f3f359fd35991af3d30bac52c57d265a3c461074cb4dc" "checksum unreachable 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "1f2ae5ddb18e1c92664717616dd9549dde73f539f01bd7b77c2edb2446bdff91" -"checksum url 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "f5ba8a749fb4479b043733416c244fa9d1d3af3d7c23804944651c8a448cb87e" +"checksum url 1.4.1 (registry+https://github.com/rust-lang/crates.io-index)" = "3e2ba3456fbe5c0098cb877cf08b92b76c3e18e0be9e47c35b487220d377d24e" "checksum user32-sys 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)" = "4ef4711d107b21b410a3a974b1204d9accc8b10dad75d8324b5d755de1617d47" "checksum utf8-ranges 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)" = "a1ca13c08c41c9c3e04224ed9ff80461d97e121589ff27c753a16cb10830ae0f" "checksum utf8-ranges 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "662fab6525a98beff2921d7f61a39e7d59e0b425ebc7d0d9e66d316e55124122" diff --git a/src/bin/cargo.rs b/src/bin/cargo.rs index 09f03ef20..23085116d 100644 --- a/src/bin/cargo.rs +++ b/src/bin/cargo.rs @@ -337,7 +337,7 @@ fn execute_external_subcommand(config: &Config, cmd: &str, args: &[String]) -> C return Err(CliError::code(code)); } } - Err(CliError::new(err, 101)) + Err(CliError::new(err, 101)) } /// List all runnable commands diff --git a/src/cargo/core/resolver/mod.rs b/src/cargo/core/resolver/mod.rs index 987fac1e4..29c464ae8 100644 --- a/src/cargo/core/resolver/mod.rs +++ b/src/cargo/core/resolver/mod.rs @@ -49,6 +49,7 @@ use std::cmp::Ordering; use std::collections::{HashSet, HashMap, BinaryHeap, BTreeMap}; use std::iter::FromIterator; use std::fmt; +use std::mem; use std::ops::Range; use std::rc::Rc; @@ -71,7 +72,7 @@ mod encode; /// /// Each instance of `Resolve` also understands the full set of features used /// for each package. -#[derive(PartialEq, Eq, Clone)] +#[derive(Clone)] pub struct Resolve { graph: Graph, replacements: HashMap, @@ -103,12 +104,12 @@ pub enum Method<'a> { // Information about the dependencies for a crate, a tuple of: // // (dependency info, candidates, features activated) -type DepInfo = (Dependency, Vec, Vec); +type DepInfo = (Dependency, Rc>, Rc>); #[derive(Clone)] struct Candidate { - summary: Rc, - replace: Option>, + summary: Summary, + replace: Option, } impl Resolve { @@ -256,12 +257,43 @@ impl<'a> Iterator for DepsNotReplaced<'a> { } } +enum RcList { + Data(Rc<(T, RcList)>), + Empty, +} + +impl RcList { + fn new() -> RcList { + RcList::Empty + } + + fn push(&mut self, data: T) { + let node = Rc::new((data, mem::replace(self, RcList::Empty))); + *self = RcList::Data(node); + } +} + +// Not derived to avoid `T: Clone` +impl Clone for RcList { + fn clone(&self) -> RcList { + match *self { + RcList::Data(ref d) => RcList::Data(d.clone()), + RcList::Empty => RcList::Empty, + } + } +} + +enum GraphNode { + Add(PackageId), + Link(PackageId, PackageId), +} + #[derive(Clone)] struct Context<'a> { - activations: HashMap<(String, SourceId), Vec>>, - resolve_graph: Graph, + activations: HashMap>>, + resolve_graph: RcList, resolve_features: HashMap>, - resolve_replacements: HashMap, + resolve_replacements: RcList<(PackageId, PackageId)>, replacements: &'a [(PackageIdSpec, Dependency)], } @@ -270,9 +302,9 @@ pub fn resolve(summaries: &[(Summary, Method)], replacements: &[(PackageIdSpec, Dependency)], registry: &mut Registry) -> CargoResult { let cx = Context { - resolve_graph: Graph::new(), + resolve_graph: RcList::new(), resolve_features: HashMap::new(), - resolve_replacements: HashMap::new(), + resolve_replacements: RcList::new(), activations: HashMap::new(), replacements: replacements, }; @@ -280,15 +312,19 @@ pub fn resolve(summaries: &[(Summary, Method)], let cx = activate_deps_loop(cx, registry, summaries)?; let mut resolve = Resolve { - graph: cx.resolve_graph, + graph: cx.graph(), empty_features: HashSet::new(), - features: cx.resolve_features, checksums: HashMap::new(), metadata: BTreeMap::new(), - replacements: cx.resolve_replacements, + replacements: cx.resolve_replacements(), + features: cx.resolve_features.iter().map(|(k, v)| { + (k.clone(), v.clone()) + }).collect(), }; - for summary in cx.activations.values().flat_map(|v| v.iter()) { + for summary in cx.activations.values() + .flat_map(|v| v.values()) + .flat_map(|v| v.iter()) { let cksum = summary.checksum().map(|s| s.to_string()); resolve.checksums.insert(summary.package_id().clone(), cksum); } @@ -307,21 +343,21 @@ pub fn resolve(summaries: &[(Summary, Method)], /// iterate through next. fn activate(cx: &mut Context, registry: &mut Registry, - parent: Option<&Rc>, + parent: Option<&Summary>, candidate: Candidate, method: &Method) -> CargoResult> { if let Some(parent) = parent { - cx.resolve_graph.link(parent.package_id().clone(), - candidate.summary.package_id().clone()); + cx.resolve_graph.push(GraphNode::Link(parent.package_id().clone(), + candidate.summary.package_id().clone())); } let activated = cx.flag_activated(&candidate.summary, method); let candidate = match candidate.replace { Some(replace) => { - cx.resolve_replacements.insert(candidate.summary.package_id().clone(), - replace.package_id().clone()); + cx.resolve_replacements.push((candidate.summary.package_id().clone(), + replace.package_id().clone())); if cx.flag_activated(&replace, method) && activated { return Ok(None); } @@ -342,40 +378,47 @@ fn activate(cx: &mut Context, Ok(Some(DepsFrame { parent: candidate, - remaining_siblings: RcVecIter::new(deps), + remaining_siblings: RcVecIter::new(Rc::new(deps)), })) } -#[derive(Clone)] struct RcVecIter { vec: Rc>, rest: Range, } impl RcVecIter { - fn new(vec: Vec) -> RcVecIter { + fn new(vec: Rc>) -> RcVecIter { RcVecIter { rest: 0..vec.len(), - vec: Rc::new(vec), + vec: vec, } } fn cur_index(&self) -> usize { self.rest.start - 1 } +} - fn as_slice(&self) -> &[T] { - &self.vec[self.rest.start..self.rest.end] +// Not derived to avoid `T: Clone` +impl Clone for RcVecIter { + fn clone(&self) -> RcVecIter { + RcVecIter { + vec: self.vec.clone(), + rest: self.rest.clone(), + } } } impl Iterator for RcVecIter where T: Clone { type Item = (usize, T); + fn next(&mut self) -> Option<(usize, T)> { self.rest.next().and_then(|i| { self.vec.get(i).map(|val| (i, val.clone())) }) } + fn size_hint(&self) -> (usize, Option) { self.rest.size_hint() } @@ -383,7 +426,7 @@ impl Iterator for RcVecIter where T: Clone { #[derive(Clone)] struct DepsFrame { - parent: Rc, + parent: Summary, remaining_siblings: RcVecIter, } @@ -395,7 +438,7 @@ impl DepsFrame { /// number of candidates at the front, so we just return the number of /// candidates in that entry. fn min_candidates(&self) -> usize { - self.remaining_siblings.as_slice().get(0).map(|&(_, ref candidates, _)| { + self.remaining_siblings.clone().next().map(|(_, (_, candidates, _))| { candidates.len() }).unwrap_or(0) } @@ -427,10 +470,33 @@ impl Ord for DepsFrame { struct BacktrackFrame<'a> { context_backup: Context<'a>, deps_backup: BinaryHeap, - remaining_candidates: RcVecIter, - parent: Rc, + remaining_candidates: RemainingCandidates, + parent: Summary, dep: Dependency, - features: Vec, + features: Rc>, +} + +#[derive(Clone)] +struct RemainingCandidates { + remaining: RcVecIter, +} + +impl RemainingCandidates { + fn next(&mut self, prev_active: &[Summary]) -> Option { + // Filter the set of candidates based on the previously activated + // versions for this dependency. We can actually use a version if it + // precisely matches an activated version or if it is otherwise + // incompatible with all other activated versions. Note that we + // define "compatible" here in terms of the semver sense where if + // the left-most nonzero digit is the same they're considered + // compatible. + self.remaining.by_ref().map(|p| p.1).filter(|b| { + prev_active.iter().any(|a| *a == b.summary) || + prev_active.iter().all(|a| { + !compatible(a.version(), b.summary.version()) + }) + }).next() + } } /// Recursively activates the dependencies for `top`, in depth-first order, @@ -453,8 +519,7 @@ fn activate_deps_loop<'a>(mut cx: Context<'a>, let mut remaining_deps = BinaryHeap::new(); for &(ref summary, ref method) in summaries { debug!("initial activation: {}", summary.package_id()); - let summary = Rc::new(summary.clone()); - let candidate = Candidate { summary: summary, replace: None }; + let candidate = Candidate { summary: summary.clone(), replace: None }; remaining_deps.extend(activate(&mut cx, registry, None, candidate, method)?); } @@ -475,7 +540,7 @@ fn activate_deps_loop<'a>(mut cx: Context<'a>, while let Some(mut deps_frame) = remaining_deps.pop() { let frame = match deps_frame.remaining_siblings.next() { Some(sibling) => { - let parent = deps_frame.parent.clone(); + let parent = Summary::clone(&deps_frame.parent); remaining_deps.push(deps_frame); (parent, sibling) } @@ -484,26 +549,18 @@ fn activate_deps_loop<'a>(mut cx: Context<'a>, let (mut parent, (mut cur, (mut dep, candidates, mut features))) = frame; assert!(!remaining_deps.is_empty()); - let my_candidates = { + let (next, has_another, remaining_candidates) = { let prev_active = cx.prev_active(&dep); trace!("{}[{}]>{} {} candidates", parent.name(), cur, dep.name(), candidates.len()); trace!("{}[{}]>{} {} prev activations", parent.name(), cur, dep.name(), prev_active.len()); - - // Filter the set of candidates based on the previously activated - // versions for this dependency. We can actually use a version if it - // precisely matches an activated version or if it is otherwise - // incompatible with all other activated versions. Note that we - // define "compatible" here in terms of the semver sense where if - // the left-most nonzero digit is the same they're considered - // compatible. - candidates.iter().filter(|&b| { - prev_active.iter().any(|a| *a == b.summary) || - prev_active.iter().all(|a| { - !compatible(a.version(), b.summary.version()) - }) - }).cloned().collect() + let mut candidates = RemainingCandidates { + remaining: RcVecIter::new(Rc::clone(&candidates)), + }; + (candidates.next(prev_active), + candidates.clone().next(prev_active).is_some(), + candidates) }; // Alright, for each candidate that's gotten this far, it meets the @@ -518,19 +575,20 @@ fn activate_deps_loop<'a>(mut cx: Context<'a>, // This means that we're going to attempt to activate each candidate in // turn. We could possibly fail to activate each candidate, so we try // each one in turn. - let mut remaining_candidates = RcVecIter::new(my_candidates); - let candidate = match remaining_candidates.next() { - Some((_, candidate)) => { + let candidate = match next { + Some(candidate) => { // We have a candidate. Add an entry to the `backtrack_stack` so // we can try the next one if this one fails. - backtrack_stack.push(BacktrackFrame { - context_backup: cx.clone(), - deps_backup: remaining_deps.clone(), - remaining_candidates: remaining_candidates, - parent: parent.clone(), - dep: dep.clone(), - features: features.clone(), - }); + if has_another { + backtrack_stack.push(BacktrackFrame { + context_backup: Context::clone(&cx), + deps_backup: >::clone(&remaining_deps), + remaining_candidates: remaining_candidates, + parent: Summary::clone(&parent), + dep: Dependency::clone(&dep), + features: Rc::clone(&features), + }); + } candidate } None => { @@ -576,19 +634,32 @@ fn activate_deps_loop<'a>(mut cx: Context<'a>, fn find_candidate<'a>(backtrack_stack: &mut Vec>, cx: &mut Context<'a>, remaining_deps: &mut BinaryHeap, - parent: &mut Rc, + parent: &mut Summary, cur: &mut usize, dep: &mut Dependency, - features: &mut Vec) -> Option { + features: &mut Rc>) -> Option { while let Some(mut frame) = backtrack_stack.pop() { - if let Some((_, candidate)) = frame.remaining_candidates.next() { - *cx = frame.context_backup.clone(); - *remaining_deps = frame.deps_backup.clone(); - *parent = frame.parent.clone(); + let (next, has_another) = { + let prev_active = frame.context_backup.prev_active(&frame.dep); + (frame.remaining_candidates.next(prev_active), + frame.remaining_candidates.clone().next(prev_active).is_some()) + }; + if let Some(candidate) = next { + if has_another { + *cx = frame.context_backup.clone(); + *remaining_deps = frame.deps_backup.clone(); + *parent = frame.parent.clone(); + *dep = frame.dep.clone(); + *features = frame.features.clone(); + backtrack_stack.push(frame); + } else { + *cx = frame.context_backup; + *remaining_deps = frame.deps_backup; + *parent = frame.parent; + *dep = frame.dep; + *features = frame.features; + } *cur = remaining_deps.peek().unwrap().remaining_siblings.cur_index(); - *dep = frame.dep.clone(); - *features = frame.features.clone(); - backtrack_stack.push(frame); return Some(candidate) } } @@ -599,7 +670,7 @@ fn activation_error(cx: &Context, registry: &mut Registry, parent: &Summary, dep: &Dependency, - prev_active: &[Rc], + prev_active: &[Summary], candidates: &[Candidate]) -> CargoError { if candidates.len() > 0 { let mut msg = format!("failed to select a version for `{}` \ @@ -608,9 +679,10 @@ fn activation_error(cx: &Context, previously selected versions of `{}`", dep.name(), parent.name(), dep.name()); + let graph = cx.graph(); 'outer: for v in prev_active.iter() { - for node in cx.resolve_graph.iter() { - let edges = match cx.resolve_graph.edges(node) { + for node in graph.iter() { + let edges = match graph.edges(node) { Some(edges) => edges, None => continue, }; @@ -644,7 +716,8 @@ fn activation_error(cx: &Context, // allows any version so we can give some nicer error reporting // which indicates a few versions that were actually found. let all_req = semver::VersionReq::parse("*").unwrap(); - let new_dep = dep.clone_inner().set_version_req(all_req).into_dependency(); + let mut new_dep = dep.clone(); + new_dep.set_version_req(all_req); let mut candidates = match registry.query(&new_dep) { Ok(candidates) => candidates, Err(e) => return e, @@ -721,8 +794,8 @@ fn compatible(a: &semver::Version, b: &semver::Version) -> bool { // The all used features set is the set of features which this local package had // enabled, which is later used when compiling to instruct the code what // features were enabled. -fn build_features(s: &Summary, method: &Method) - -> CargoResult<(HashMap>, HashSet)> { +fn build_features<'a>(s: &'a Summary, method: &'a Method) + -> CargoResult<(HashMap<&'a str, Vec>, HashSet<&'a str>)> { let mut deps = HashMap::new(); let mut used = HashSet::new(); let mut visited = HashSet::new(); @@ -754,10 +827,11 @@ fn build_features(s: &Summary, method: &Method) } return Ok((deps, used)); - fn add_feature(s: &Summary, feat: &str, - deps: &mut HashMap>, - used: &mut HashSet, - visited: &mut HashSet) -> CargoResult<()> { + fn add_feature<'a>(s: &'a Summary, + feat: &'a str, + deps: &mut HashMap<&'a str, Vec>, + used: &mut HashSet<&'a str>, + visited: &mut HashSet<&'a str>) -> CargoResult<()> { if feat.is_empty() { return Ok(()) } // If this feature is of the form `foo/bar`, then we just lookup package @@ -770,18 +844,18 @@ fn build_features(s: &Summary, method: &Method) match parts.next() { Some(feat) => { let package = feat_or_package; - used.insert(package.to_string()); - deps.entry(package.to_string()) + used.insert(package); + deps.entry(package) .or_insert(Vec::new()) .push(feat.to_string()); } None => { let feat = feat_or_package; - if !visited.insert(feat.to_string()) { + if !visited.insert(feat) { bail!("Cyclic feature dependency: feature `{}` depends \ on itself", feat) } - used.insert(feat.to_string()); + used.insert(feat); match s.features().get(feat) { Some(recursive) => { for f in recursive { @@ -789,10 +863,10 @@ fn build_features(s: &Summary, method: &Method) } } None => { - deps.entry(feat.to_string()).or_insert(Vec::new()); + deps.entry(feat).or_insert(Vec::new()); } } - visited.remove(&feat.to_string()); + visited.remove(feat); } } Ok(()) @@ -804,13 +878,16 @@ impl<'a> Context<'a> { // // Returns if this summary with the given method is already activated. fn flag_activated(&mut self, - summary: &Rc, + summary: &Summary, method: &Method) -> bool { let id = summary.package_id(); - let key = (id.name().to_string(), id.source_id().clone()); - let prev = self.activations.entry(key).or_insert(Vec::new()); + let prev = self.activations + .entry(id.name().to_string()) + .or_insert_with(HashMap::new) + .entry(id.source_id().clone()) + .or_insert(Vec::new()); if !prev.iter().any(|c| c == summary) { - self.resolve_graph.add(id.clone(), &[]); + self.resolve_graph.push(GraphNode::Add(id.clone())); prev.push(summary.clone()); return false } @@ -851,7 +928,7 @@ impl<'a> Context<'a> { candidates.sort_by(|a, b| { b.summary.version().cmp(a.summary.version()) }); - Ok((dep, candidates, features)) + Ok((dep, Rc::new(candidates), Rc::new(features))) }).collect::>>()?; // Attempt to resolve dependencies with fewer candidates before trying @@ -873,7 +950,7 @@ impl<'a> Context<'a> { registry: &mut Registry, dep: &Dependency) -> CargoResult> { let summaries = registry.query(dep)?; - summaries.into_iter().map(Rc::new).map(|summary| { + summaries.into_iter().map(|summary| { // get around lack of non-lexical lifetimes let summary2 = summary.clone(); @@ -913,7 +990,7 @@ impl<'a> Context<'a> { debug!("Preventing\n{:?}\nfrom replacing\n{:?}", summary, s); None } else { - Some(Rc::new(s)) + Some(s) }; let matched_spec = spec.clone(); @@ -932,13 +1009,17 @@ impl<'a> Context<'a> { }).collect() } - fn prev_active(&self, dep: &Dependency) -> &[Rc] { - let key = (dep.name().to_string(), dep.source_id().clone()); - self.activations.get(&key).map(|v| &v[..]).unwrap_or(&[]) + fn prev_active(&self, dep: &Dependency) -> &[Summary] { + self.activations.get(dep.name()) + .and_then(|v| v.get(dep.source_id())) + .map(|v| &v[..]) + .unwrap_or(&[]) } - fn resolve_features(&mut self, candidate: &Summary, method: &Method) - -> CargoResult)>> { + fn resolve_features<'b>(&mut self, + candidate: &'b Summary, + method: &'b Method) + -> CargoResult)>> { let dev_deps = match *method { Method::Everything => true, Method::Required { dev_deps, .. } => dev_deps, @@ -949,7 +1030,7 @@ impl<'a> Context<'a> { let deps = deps.iter().filter(|d| d.is_transitive() || dev_deps); let (mut feature_deps, used_features) = build_features(candidate, - method)?; + method)?; let mut ret = Vec::new(); // Next, sanitize all requested features by whitelisting all the @@ -960,7 +1041,7 @@ impl<'a> Context<'a> { continue } let mut base = feature_deps.remove(dep.name()).unwrap_or(vec![]); - base.extend(dep.features().iter().map(|x| x.clone())); + base.extend(dep.features().iter().cloned()); for feature in base.iter() { if feature.contains("/") { bail!("feature names may not contain slashes: `{}`", feature); @@ -986,21 +1067,51 @@ impl<'a> Context<'a> { // Record what list of features is active for this package. if !used_features.is_empty() { let pkgid = candidate.package_id(); - self.resolve_features.entry(pkgid.clone()) - .or_insert(HashSet::new()) - .extend(used_features); + + let mut set = self.resolve_features.entry(pkgid.clone()) + .or_insert_with(HashSet::new); + for feature in used_features { + if !set.contains(feature) { + set.insert(feature.to_string()); + } + } } Ok(ret) } + + fn resolve_replacements(&self) -> HashMap { + let mut replacements = HashMap::new(); + let mut cur = &self.resolve_replacements; + while let RcList::Data(ref d) = *cur { + let (k, v) = d.0.clone(); + replacements.insert(k, v); + cur = &d.1; + } + return replacements + } + + fn graph(&self) -> Graph { + let mut graph = Graph::new(); + let mut cur = &self.resolve_graph; + while let RcList::Data(ref d) = *cur { + match d.0 { + GraphNode::Add(ref p) => graph.add(p.clone(), &[]), + GraphNode::Link(ref a, ref b) => graph.link(a.clone(), b.clone()), + } + cur = &d.1; + } + return graph + } } fn check_cycles(resolve: &Resolve, - activations: &HashMap<(String, SourceId), Vec>>) + activations: &HashMap>>) -> CargoResult<()> { let summaries: HashMap<&PackageId, &Summary> = activations.values() + .flat_map(|v| v.values()) .flat_map(|v| v) - .map(|s| (s.package_id(), &**s)) + .map(|s| (s.package_id(), s)) .collect(); // Sort packages to produce user friendly deterministic errors. diff --git a/src/cargo/lib.rs b/src/cargo/lib.rs index 5bce0e59e..8e723a9a4 100755 --- a/src/cargo/lib.rs +++ b/src/cargo/lib.rs @@ -224,7 +224,7 @@ fn handle_cause(cargo_err: E, shell: &mut MultiShell) -> bool //the borrow's actual lifetime for purposes of downcasting and //inspecting the error chain unsafe fn extend_lifetime(r: &Error) -> &(Error + 'static) { - std::mem::transmute::<&Error, &Error>(r) + std::mem::transmute::<&Error, &Error>(r) } let verbose = shell.get_verbose(); diff --git a/src/cargo/util/graph.rs b/src/cargo/util/graph.rs index 6543c8f91..984daa87d 100644 --- a/src/cargo/util/graph.rs +++ b/src/cargo/util/graph.rs @@ -21,7 +21,9 @@ impl Graph { } pub fn add(&mut self, node: N, children: &[N]) { - self.nodes.insert(node, children.iter().cloned().collect()); + self.nodes.entry(node) + .or_insert_with(HashSet::new) + .extend(children.iter().cloned()); } pub fn link(&mut self, node: N, child: N) { diff --git a/tests/resolve.rs b/tests/resolve.rs index 873220848..e0d19c4b1 100644 --- a/tests/resolve.rs +++ b/tests/resolve.rs @@ -18,7 +18,9 @@ fn resolve(pkg: PackageId, deps: Vec, -> CargoResult> { let summary = Summary::new(pkg.clone(), deps, HashMap::new()).unwrap(); let method = Method::Everything; - Ok(resolver::resolve(&[(summary, method)], &[], registry)?.iter().cloned().collect()) + let resolve = resolver::resolve(&[(summary, method)], &[], registry)?; + let res = resolve.iter().cloned().collect(); + Ok(res) } trait ToDep { -- 2.30.2